﻿#include <iostream>
#include<vector>

using namespace std;

//如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，
// 导致没有复写的数「被覆盖掉」。
// 因此我们选择「从后往前」的复写策略。
//但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」
// 因此我们的大体流程分两步：
//i.先找到最后⼀个复写的数；
//ii.然后从后向前进⾏复写操作。
// 
//算法流程：
//a.初始化两个指针 cur = 0 ， dest = 0 ；
//b.找到最后⼀个复写的数：
//i.当 cur < n 的时候，⼀直执⾏下⾯循环：
//    • 判断 cur 位置的元素 :
//◦ 如果是 0 的话， dest 往后移动两位；
//◦ 否则， dest 往后移动⼀位。
//• 判断 dest 时候已经到结束位置，如果结束就终⽌循环；
//• 如果没有结束， cur++ ，继续判断。
//c.判断 dest 是否越界到 n 的位置：
//i.如果越界，执⾏下⾯三步：
//1. n - 1 位置的值修改成 0 ；
//2. cur 向移动⼀步；
//3. dest 向前移动两步。
//d.从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
//i.判断 cur 位置的值：
//1. 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；
//2. 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；
//ii.cur-- ，复写下⼀个位置。

class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        int dest = -1, cur = 0;
        while (cur < arr.size())
        {
            if (arr[cur] != 0)
            {
                ++dest;
            }
            else
            {
                dest += 2;
            }
            if (dest >= arr.size() - 1)
            {
                break;
            }
            cur++;
        }
        if (dest == arr.size())
        {
            arr[arr.size() - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0)
        {
            if (arr[cur] != 0)
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                arr[dest--] = arr[dest--] = 0;
                cur--;
            }
        }
    }
};